#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int v, n, t;
int g[205][205];
int i, j, k;
int w[N], z[N];
int b[N];
int f[N];
int main() {
    cin >> v >> n;
    for (i = 1; i <= n; i++) {
        int x;
        cin >> w[i] >> z[i] >> x;
        t = max(t, x);
        b[x]++;
        g[x][b[x]] = i;
    }
    for (i = 1; i <= t; i++) {
        for (j = v; j >= 0; j--) {
            for (k = 1; k <= b[i]; k++) {
                if (j >= w[g[i][k]]) {
                    f[j] = max(f[j], f[j - w[g[i][k]]] + z[g[i][k]]);
                }
            }
        }
    }
    cout << f[v] << endl;
    return 0;
}